// Created by WXX on 2021/10/23 21:09
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {

        int n = heights.size();
        vector<int> h(n + 2);
        h[0] = h[n + 1] = -1;  // 哨兵
        for (int i = 1; i <= n; i++) h[i] = heights[i - 1];

        stack<int> stk;
        int l[n + 1];  // l[i]:左边第一个小于h[i]的数据对应的下标
        int r[n + 1];  // r[i]:右边第一个小于h[i]的数据对应的下标

        stk.push(0);  // 将h[0]的下标放入栈，这样就不用判断栈是否为空了
        for (int i = 1; i <= n; i++) {
            while (h[stk.top()] >= h[i]) stk.pop();
            l[i] = stk.top();
            stk.push(i);
        }

        stk = stack<int>();  // 清空栈，不存在clear()
        stk.push(n + 1);  // 将h[n+1]的下标放入栈，这样就不用判断栈是否为空了
        for (int i = n; i; i--) {
            while (h[stk.top()] >= h[i]) stk.pop();
            r[i] = stk.top();
            stk.push(i);
        }

        int res = 0;
        for (int i = 1; i <= n; i++) res = max(res, h[i] * (r[i] - l[i] - 1));
        return res;
    }
};

int main() {

    vector<int> height = {2, 1, 5, 6, 2, 3};
    cout << Solution().largestRectangleArea(height) << endl;  // 10

    return 0;
}
